public class Work02 {

    /**
     * DFS算法解决走迷宫问题
     * 0: 表示通路
     * 1: 表示死路
     *
     */
    static String path = "";
    static String shortestPath = "";

    public static void dfsMaze(int x, int y, char[][] maze) {
        /*
         * 获得矩阵的大小
         * */
        int m=maze.length;
        int n=maze[0].length;
        //设置结束条件
        if (x < 0 || y < 0)
            return;
        // 如果坐标越界，或者 maze[x][y]==1 表示遇到障碍
        if (x > m - 1 || y > n - 1 || maze[x][y] ==1)
            return;
        //表示遇到障碍
        if (maze[x][y] == 1)
            return; // 判断是否通路和越界
        if (x == m - 1 && y == n - 1) { // 判断是否抵达出口
            path = path + "(" + x + "," + y + ")";
            if (shortestPath.length() == 0 || shortestPath.length() > path.length())
                shortestPath = path;
            System.out.println("找到路线:" + path);
            return;
        }

        String temp = path;
        path = path + "(" + x + "," + y + ")" + "-"; // 记录路线
        maze[x][y] = 1; // 将走过的路标记
        // 向四个方向搜索
        dfsMaze(x + 1, y, maze);  //向右搜索
        dfsMaze(x, y + 1, maze);  //向下搜索
        dfsMaze(x, y - 1, maze);  //向上搜索
        dfsMaze(x - 1, y, maze);  //向左搜索
        // 将路线和标记恢复成上一次的状态
        maze[x][y] = 0;
        //清除
        path = temp;
    }

    private static String[] nn= {
            "01010101001011001001010110010110100100001000101010",
            "00001000100000101010010000100000001001100110100101",
            "01111011010010001000001101001011100011000000010000",
            "01000000001010100011010000101000001010101011001011",
            "00011111000000101000010010100010100000101100000000",
            "11001000110101000010101100011010011010101011110111",
            "00011011010101001001001010000001000101001110000000",
            "10100000101000100110101010111110011000010000111010",
            "00111000001010100001100010000001000101001100001001",
            "11000110100001110010001001010101010101010001101000",
            "00010000100100000101001010101110100010101010000101",
            "11100100101001001000010000010101010100100100010100",
            "00000010000000101011001111010001100000101010100011",
            "10101010011100001000011000010110011110110100001000",
            "10101010100001101010100101000010100000111011101001",
            "10000000101100010000101100101101001011100000000100",
            "10101001000000010100100001000100000100011110101001",
            "00101001010101101001010100011010101101110000110101",
            "11001010000100001100000010100101000001000111000010",
            "00001000110000110101101000000100101001001000011101",
            "10100101000101000000001110110010110101101010100001",
            "00101000010000110101010000100010001001000100010101",
            "10100001000110010001000010101001010101011111010010",
            "00000100101000000110010100101001000001000000000010",
            "11010000001001110111001001000011101001011011101000",
            "00000110100010001000100000001000011101000000110011",
            "10101000101000100010001111100010101001010000001000",
            "10000010100101001010110000000100101010001011101000",
            "00111100001000010000000110111000000001000000001011",
            "10000001100111010111010001000110111010101101111000"};

    public static void main(String[] args) {
        // 初始化一个迷宫地图
        // 0: 表示通路
        // 1:表示死路
        int[][] maze = {
                {0, 0, 1, 1, 1, 1, 1, 1, 1},
                {1, 0, 0, 0, 0, 0, 0, 0, 1},
                {1, 0, 1, 1, 0, 1, 1, 0, 1},
                {1, 0, 1, 0, 0, 1, 0, 0, 1},
                {1, 0, 1, 0, 1, 0, 1, 0, 1},
                {1, 0, 0, 0, 0, 0, 1, 0, 1},
                {1, 1, 0, 1, 1, 0, 1, 1, 1},
                {1, 0, 0, 0, 0, 0, 0, 0, 0},
                {1, 1, 1, 1, 1, 1, 1, 1, 0}
        };

        int[][] maze2 = {
                {0, 0, 1, 1, 1, 1, 1, 1, 1},
                {1, 0, 0, 0, 0, 0, 0, 0, 1},
                {1, 0, 1, 1, 0, 1, 1, 0, 1},
                {1, 0, 1, 0, 0, 1, 0, 0, 1},
                {1, 0, 1, 0, 1, 0, 1, 0, 1},
                {1, 0, 0, 0, 0, 0, 1, 0, 1},
                {1, 1, 0, 1, 1, 0, 1, 0, 1},
                {1, 0, 0, 0, 0, 0, 1, 0, 0},
                {1, 1, 1, 1, 1, 1, 1, 1, 0}
        };

        char[][] maze3 = new char[30][];

        for(int i=0;i<30;i++) {
            maze3[i]=nn[i].toCharArray();
        }
        /*
         * 从矩阵的左上角位置开始搜索
         * */
        dfsMaze(0, 0, maze3);
        if (shortestPath.length() != 0)
            System.out.println("最短路线为：" + shortestPath);
        else
            System.out.println("没有找到路线！");


    }

}
